612. Сортировка ДНК

Величиной строки будем называть количество инверсий в ней. В задаче требуется отсортировать набор строк одинаковой длины по неубыванию их величин.

Вход. Первая строка содержит количество тестов M, после которой следует пустая строка. Первая строка каждого теста содержит длину n (0 < n £ 50) и количество m (0 < m £ 100) строк. Далее следуют m строк длины n. Входные тесты разделяются пустой строкой.

Выход. Для каждого теста вывести последовательность строк от «наиболее отсортированных» до «наименее отсортированных», то есть по неубыванию количества инверсий в них. Для строк с одинаковым числом инверсий сохранить входной порядок. Между тестами выводить пустую строку.

Пример входа

1

10 6

AACATGAAGG

TTTTGGCCAA

TTTGGCCAAA

GATCAGATTT

CCCGGGGGGA

ATCGATGCAT

Пример выхода

CCCGGGGGGA

AACATGAAGG

GATCAGATTT

ATCGATGCAT

TTTTGGCCAA

TTTGGCCAAA

РЕШЕНИЕ

сортировка

Анализ алгоритма

Для каждой строки вычислим число инверсий в ней. Это число вместе с самой строкой храним в векторе пар. Выполняем стабильную сортировку строк в порядке неубывания количества инверсий в них и выводим результат.

Реализация алгоритма

Строки вместе с количеством инверсий в них храним в векторе пар s.

vector<pair<string,int> > s;

Функция value вычисляет количество инверсий в строке s.

int value(string s)

{

int i, j, res = 0;

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

if (s[i] > s[j]) res++;

return res;

}

Функция lt используется в стабильной сортировке строк.

int lt(pair<string,int> x, pair<string,int> y)

{

return (x.second < y.second);

}

Основной цикл программы. Читаем количество входных тестов tests.

scanf("%d",&tests);

while(tests--)

{

s.clear();

Для каждого теста читаем значения n и m. Для каждой строки вычисляем число инверсий в ней, заносим их структуру типа DNA и сохраняем в векторе s.

scanf("%d %d\n",&n,&m);

for(i = 0; i < m; i++)

{

gets(stroka);

s.push_back(make_pair(stroka,value(stroka)));

}

Проводим стабильную сортировку строк.

stable_sort(s.begin(),s.end(),lt);

Выводим результат. Между тестами выводим пустую строку.

for(iter = s.begin();iter != s.end();iter++)

puts((*iter).first.c_str());

if (tests) printf("\n");

}